/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: WHY
 * Date: 2022-11-08
 * Time: 16:39
 */
import java.util.*;
//反转链表
public class Solution {


    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */


        /**
         *
         * @param head ListNode类
         * @param m int整型
         * @param n int整型
         * @return ListNode类
         */
        public ListNode reverseBetween (ListNode head, int m, int n) {
            // write code here
            //设置虚拟头结点
            ListNode retNode = new ListNode(-1);
            retNode.next = head;

            ListNode pre = retNode;
            //1.走到left的前一个节点
            for(int i=0;i<m-1;i++){
                pre = pre.next;
            }

            //到right节点
            ListNode rigthNode = pre;
            for(int i=0;i<n-m+1;i++){
                rigthNode = rigthNode.next;
            }

            //3.截取出一个子链表
            ListNode leftNode = pre.next;
            ListNode cur = rigthNode.next;

            //4.切断连接
            pre.next=null;
            rigthNode.next=null;

            //5.反转局部链表
            reverseLinkedList(leftNode);

            //6.接回原来的链表
            pre.next = rigthNode;
            leftNode.next = cur;
            return retNode.next;
        }

        private void reverseLinkedList(ListNode head){
            ListNode pre = null;
            ListNode cur = head;
            while(cur!=null){
                //Cur_next 指向cur节点的下一个节点
                ListNode Cur = cur.next;
                cur.next = pre;
                pre = cur;
                cur = Cur ;
            }
        }
    }


